package _17_剑指Offer;

import _17_剑指Offer.datastrcute.ListNode;

// 链表问题，可以思考使用快慢指针解决
public class _22_剑指Offer链表中倒数第k个节点 {

    // 快慢指针
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 先让块指针，指向k项，慢指针指向起始位置
        ListNode slow = head;
        ListNode fast = head;
        while (--k >= 0) {
            fast = fast.next;
        }

        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    // 递归
    int k;

    public ListNode getKthFromEnd1(ListNode head, int k) {
        this.k = k;
        return getKthFromEnd(head);
    }

    private ListNode getKthFromEnd(ListNode head) {
        if (head == null) return null;

        ListNode newHead = getKthFromEnd(head.next);
        if (k >= 0) {
            k--;
        }
        return k == -1 ? newHead : head;
    }

}
